Demystifying Latschev’s Theorem for Manifold Reconstruction

SoCG 2024

Sush Majhi
George Washington University, USA

Today’s Agenda

  • The problem of shape reconstruction
  • Vietoris–Rips complexes
  • Theorems of Hausmann and Latschev
  • Demystifying Latschev’s theorem
    • Jung’s theorem on manifolds
    • Simplicial subdivision
  • Questions

The Problem of Shape Reconstruction

  • Shape: A Shape is modeled as a metric space \((M,d_M)\).

    • general compact set

    • metric graph

    • for today, \(M\) is a closed Riemannian manifold.

  • Sample: A finite metric space \((X,d_X)\) close to \(M\).

    • small Hausdorff proximity if \(M\) is a Euclidean submanifold and \(X\subset\mathbb R^d\)

    • for today, small Gromov–Hausdorff distance.

  • Goal: Infer the topology of \(M\) from \(X\).

    • Estimate only the Betti numbers: number of connected components, cycles, voids, etc, of \(M\).

    • for today, construct a topological space \(\widetilde{M}\) from \(X\) to retain the topology of \(M\), i.e., \(M\simeq\widetilde{M}\).

Vietoris–Rips Complex

  • a metric space \((X,d_X)\)

  • a scale \(\beta>0\)

  • \(\mathcal{R}_\beta(X)\) is an abstract simplicial complex such that

    • each subset \(A\subset X\) of size \(k\) with diameter at most \(\beta\) is a \((k-1)\)-simplex.

Hausmann’s Theorem

Convexity Radius

  • the largest (sup) radius so that geodesic balls are convex.

    • for the circle, it is a quarter of the circumference

    • denoted by \(\rho(M)\)

    • \(\rho(M)>0\) for a compact manifold

Theorem (Hausmann 1995): For any \(0<\beta<\rho(M)\), the Vietoris–Rips complex \(\mathcal{R}_\beta(M)\) is homotopy equivalent to \(M\).

  • vertex set is the entire manifold \(M\)
  • Question: what about the Vietoris–Rips complex of a dense subset \(X\subset M\)?
    • more generally, for a sample with a small \(d_{GH}(M,X)\).

Finite Reconstruction Problem

Gromov–Hausdorff Distance:

  • provides the noise model for our reconstruction problem
  • similarity measure between abstract metric spaces \((X,d_X)\) and \((Y,d_Y)\)
  • Definition: \(d_{GH(X,Y)}=\inf d_H^Z(f(X),g(Y))\)
    • inf over metric spaces \((Z,d_Z)\) and isometries \(f:X\to Z\), \(g:Y\to Z\)

See (Adams et al. 2023) for more details on the relation between the Gromov–Hausdorff and Hausdorff distances.

Demystifying Latschev’s Theorem

Latschev’s Theorem (Latschev 2001):

For every closed Riemannian manifold \(M\), there exists a positive number \(\epsilon_0\) such that for any \(0<\beta\leq\epsilon_0\) there exists some \(\delta>0\) such that for every metric space \(X\) with Gromov–Hausdorff distance to \(M\) less than \(\delta\), the Vietoris–Rips complex \(\mathcal R_\beta(X)\) is homotopy equivalent to \(M\).

Key points:

  • The result is qualitative

  • the threshold \(\epsilon_0=\epsilon_0(M)\) depends solely on the geometry of \(M\). But the theorem did not say how!

  • \(\delta=\delta(\beta)\) is a function (probably a fraction) of \(\beta\).

  • Nonetheless, the result answers Hausmann’s question!

Quantitative Latschev’s Theorem

Metric Graph Reconstruction (Majhi 2023)

Let \((G,d_G)\) be a compact, path-connected metric graph, \((X,d_X)\) a metric space, and \(\beta>0\) a number such that \[3d_{GH}(G,X)<\beta<3\rho(G)/4.\] Then, \(\mathcal R_\beta(X)\simeq G\).

Key points:

  • The result is quantitative

  • \(\epsilon_0=3\rho(G)/4\)

  • \(\delta=\beta/3\)

Quantitative Latschev’s Theorem

Riemannian Manifold Reconstruction (Majhi 2024)

Let \((M,d_M)\) be a closed, connected Riemannian manifold. Let \((X,d_X)\) be a compact metric space and \(\beta>0\) a number such that \[ \frac{1}{\zeta}d_{GH}(M,X)<\beta<\frac{1}{1+2\zeta}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\} \] for some \(0<\zeta\leq1/14\). Then, \(\mathcal R_\beta(X)\simeq M\).

Key points:

  • \(\kappa\) is an upper bound on the sectional curvatures of \(M\)

  • For \(\zeta=\frac{1}{14}\):

    • \(\epsilon_0=\frac{7}{8}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\}\)

    • \(\delta=\frac{\beta}{14}\)

Quantitative Latschev’s Theorem

Euclidean Submanifold Reconstruction (Majhi 2024)

Let \(M\subset\mathbb R^N\) be a closed, connected submanifold. Let \(X\subset\mathbb R^N\) be a compact subset and \(\beta>0\) a number such that \[ \frac{1}{\zeta}d_{H}(M,X)<\beta<\frac{3(1+2\zeta)(1-14\zeta)}{8(1-2\zeta)^2}\tau(M) \] for some \(0<\zeta<1/14\). Then, \(\mathcal R_\beta(X)\simeq M\).

Key points:

  • \(\tau(M)\) is the reach of \(M\)

  • For \(\zeta=\frac{1}{28}\):

    • \(\epsilon_0=\frac{315}{1352}\tau(M)\)

    • \(\delta=\frac{\beta}{28}\)

Discussions

References

Adams, Henry, Florian Frick, Sushovan Majhi, and Nicholas McBride. 2023. “Hausdorff Vs Gromov–Hausdorff Distances.” arXiv Preprint arXiv:2309.16648.
Chazal, Frédéric, Ruqi Huang, and Jian Sun. 2015. “Gromov–Hausdorff Approximation of Filamentary Structures Using Reeb-Type Graphs.” Discrete & Computational Geometry 53 (3): 621–49. https://doi.org/10.1007/s00454-015-9674-1.
Ge, Xiaoyin, Issam Safa, Mikhail Belkin, and Yusu Wang. 2011. “Data Skeletonization via Reeb Graphs.” In Advances in Neural Information Processing Systems. Vol. 24. Curran Associates, Inc.
Hausmann, Jean-Claude. 1995. “On the Vietoris-Rips Complexes and a Cohomology Theory for Metric Spaces.” In Prospects in Topology (AM-138), 175–88. Princeton University Press.
Komendarczyk, Rafal, Sushovan Majhi, and Will Tran. 2024. “Topological Stability and Latschev-Type Reconstruction Theorems for \(\boldsymbol{\mathrm{CAT}(κ)}\) Spaces.”
Latschev, J. 2001. “Vietoris-Rips Complexes of Metric Spaces Near a Closed Riemannian Manifold.” Archiv Der Mathematik 77 (6): 522–28. https://doi.org/10.1007/PL00000526.
Majhi, Sushovan. 2023. “VietorisRips Complexes of Metric Spaces Near a Metric Graph.” Journal of Applied and Computational Topology, May. https://doi.org/10.1007/s41468-023-00122-z.
———. 2024. “Demystifying Latschev’s Theorem: Manifold Reconstruction from Noisy Data.” Discrete & Computational Geometry, May. https://doi.org/10.1007/s00454-024-00655-9.